 #define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef Node* DataType;
typedef struct Node {
	struct Node* next;
	DataType x;
}Node;

typedef struct Queue {
	Node* Phead;
	Node* tail;
	int size;
}Queue;

void QueueInit(Queue* p)
{
	assert(p);
	p->Phead = p->tail = NULL;
	p->size = 0;
}

void QueueDestroy(Queue* p)
{
	assert(p);
	Node* cur = p->Phead;
	while (cur)
	{
		Node* next = cur->next;
		free(cur);
		cur = next;
	}
	p->Phead = p->tail = NULL;
	p->size = 0;
}
void Qpush(Queue* p, DataType X)
{
	assert(p);
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->x = 0;
	if (p->Phead == NULL)
	{
		p->Phead = p->tail = newNode;
	}
	else {
		p->tail->next = newNode;
		p->tail = newNode;
	}
	p->size++;
}

DataType QFront(Queue* p)
{
	assert(p);
	assert(p->Phead);
	return p->Phead->x;
}

void Qpop(Queue* p)
{
	assert(p);
	assert(p->size);
	if (p->Phead->next = NULL)
	{
		free(p->Phead);
		p->Phead = p->tail = NULL;
	}
	else
	{
		Node* next = p->Phead->next;
		free(p->Phead);
		p->Phead = next;
	}
	p->size--;
}


void TreeLevelOrder(Node* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		Qpush(&q, root);
}

bool QueueEmpty(Queue* p)
{
	assert(p);
	if (p->size == 0)
		return true;
	else
		return false;
}

void TreeLevelInorder(Node* root)
{
	Queue* p;
	QueueInit(p);
	if (root)
	{
		Qpush(p, root);
	}
	while (!QueueEmpty(p))
	{
		Node* Front = QFront(p);
		Qpop(p);
		printf("%d", Front->x);
		if (Front->left)
			Qpush(p, Front->left);
		if (Front->right)
			Qpush(p, Front->right);
	}
	QueueDestroy(p);
}